package interview.minskipcharacters;

import java.util.Arrays;
import java.util.Map;

public class MinSkipCharacters {
	public int min(String source, Map<String, Boolean> dict) {
		int[][] DP = new int[source.length()][source.length()];
		for (int i = 0; i < source.length(); i++) {
			if (dict.get(source.charAt(i) + " ") != null) {
				DP[i][i] = 0;
			} else {
				DP[i][i] = 1;
			}
		}

		for (int i = 2; i <= source.length(); i++) {
			for (int j = 0; j < source.length() - i + 1; j++) {
				char[] array = source.substring(j, j + i).toCharArray();
				Arrays.sort(array);
				String s = new String(array);
				if (dict.get(s) != null) {
					DP[j][j + i - 1] = 0;
				} else {
					int min = i + 1;
					for (int k = j; k < j + i - 1; k++) {
						if (min > DP[j][k] + DP[k + 1][j + i - 1]) {
							min = DP[j][k] + DP[k + 1][j + i - 1];
						}
					}
					DP[j][j + i - 1] = min;
				}
			}
		}

		for(int i = 0; i < source.length(); i++) {
			for(int j = 0; j < source.length(); j++) {
				System.out.print(DP[i][j] + " ");
			}
			System.out.println();
		}
		
		return DP[source.length() - 1][source.length() - 1];
	}
}
